﻿#define _CRT_SECURE_NO_WARNINGS 1


//1.  输入一个链表，输出该链表中倒数第k个结点
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

 /**
  *
  * @param pListHead ListNode类
  * @param k int整型
  * @return ListNode类
  */
  /*struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
      // write code here
      struct ListNode* slow = pListHead;
      struct ListNode* fast = pListHead;
      while (k--)
      {
          if (fast == NULL)
          {
              return fast;
          }
          fast = fast->next;
      }
      while (fast)
      {
          fast = fast->next;
          slow = slow->next;
      }

      return slow;
  }*/




  //2.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     struct ListNode *next;
   * };
   */
   /*
   struct ListNode* middleNode(struct ListNode* head)
   {
       struct ListNode* slow = head;
       struct ListNode* fast = head;
       while (fast && fast->next)
       {
           slow = slow->next;
           fast = fast->next->next;
       }
       return slow;
   }
   */

   //3.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

   /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     struct ListNode *next;
    * };
    */


    //struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
    //{
    //    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    //    struct ListNode* tail = guard;
    //    guard->next = NULL;
    //    while (list1 && list2)
    //    {
    //        if (list1->val < list2->val)
    //        {
    //            tail->next = list1;
    //            list1 = list1->next;
    //        }
    //        else
    //        {
    //            tail->next = list2;
    //            list2 = list2->next;
    //        }
    //        tail = tail->next;
    //    }
    //    if (list1 != NULL)
    //    {
    //        tail->next = list1;
    //    }
    //    if (list2 != NULL)
    //    {
    //        tail->next = list2;
    //    }
    //    struct ListNode* head = guard->next;
    //    free(guard);
    //    return head;
    //}

    //4.反转链表
    /*struct ListNode* reverseList(struct ListNode* head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        struct ListNode* newhead = NULL;
        struct ListNode* new = NULL;
        struct ListNode* cur = head->next;
        struct ListNode* pre = head;
        while (head->next)
        {
            cur = head->next;
            pre = head;
            while (cur->next)
            {
                pre = pre->next;
                cur = cur->next;
            }
            pre->next = NULL;
            if (newhead == NULL)
            {
                newhead = cur;
                new = cur;
            }
            else
            {
                new->next = cur;
                new = new->next;
            }
        }
        new->next = head;
        return newhead;
    }
    }*/


    //5.输入两个链表，找出它们的第一个公共结点

    /*/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     struct ListNode *next;
      * };
      */
      /*struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
      {
          int LA = 0;
          int LB = 0;
          struct ListNode* curA = headA;
          struct ListNode* curB = headB;
          while (curA->next)
          {
              LA++;
              curA = curA->next;
          }

          while (curB->next)
          {
              LB++;
              curB = curB->next;
          }

          if (curB != curA)
              return NULL;

          int gap = abs(LA - LB);
          struct ListNode* longlist = headA;
          struct ListNode* shortlist = headB;
          if (LB > LA)
          {
              longlist = headB;
              shortlist = headA;
          }
          while (gap--)
          {
              longlist = longlist->next;
          }
          while (longlist != shortlist)
          {
              longlist = longlist->next;
              shortlist = shortlist->next;
          }
          return longlist;

      }*/



      //6.给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
      /**
       * Definition for singly-linked list.
       * struct ListNode {
       *     int val;
       *     struct ListNode *next;
       * };
       */
       /*struct ListNode* detectCycle(struct ListNode* head)
       {
           struct ListNode* slow = head;
           struct ListNode* fast = head;
           while (fast && fast->next)
           {
               slow = slow->next;
               fast = fast->next->next;
               if (slow == fast)
               {
                   struct ListNode* meet = fast;
                   while (head != meet)
                   {
                       head = head->next;
                       meet = meet->next;
                   }
                   return meet;
               }
           }
           return NULL;

       }
       除了这么写,还可以把meet->next=otherhead,meet->next=NULL,然后让head otherhead找交点变为5的程序
       */


       //
       //给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
       //
       //构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
       //新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
       /**
        * Definition for a Node.
        * struct Node {
        *     int val;
        *     struct Node *next;
        *     struct Node *random;
        * };
        */

        /*
        struct Node* copyRandomList(struct Node* head)
        {
            struct Node* cur = head;
            while (cur)
            {
                struct Node* next = cur->next;
                struct Node* copy = (struct Node*)malloc(sizeof(struct Node));


                copy->val = cur->val;
                cur->next = copy;
                copy->next = next;
                cur = next;

            }
            cur = head;
            while (cur)
            {
                struct Node* copy = cur->next;
                if (cur->random == NULL)
                {
                    copy->random = NULL;
                }
                else
                {
                    copy->random = cur->random->next;
                }
                cur = copy->next;

            }

            cur = head;

            struct Node* chead = NULL;

            struct Node* ctail = NULL;
            while (cur)
            {
                struct Node* copy = cur->next;
                struct Node* next = copy->next;

                cur->next = next;

                if (ctail == NULL)
                    chead = ctail = copy;

                else
                {
                    ctail->next = copy;
                    ctail = ctail->next;
                }
                cur = next;
            }
            return chead;

        }*/